9018. n-ое число, делящееся на a или b
Даны два натуральных числа a и b. Найдите n-ое по
порядку число, которое делится либо на a,
либо на b.
Вход. Три
натуральных числа a, b и n (a, b, n ≤ 109).
Выход. Выведите
n-ое число, которое делится либо на a, либо на b. Гарантируется, что это число не превышает 109.
|
Пример
входа 1 |
Пример
выхода 1 |
|
2 5 10 |
16 |
|
|
|
|
Пример
входа 2 |
Пример
выхода 2 |
|
3 7 25 |
57 |
РЕШЕНИЕ
бинарный
поиск
Анализ алгоритма
Пусть функция f(n) вычисляет количество натуральных чисел на отрезке [1; n], которые делятся либо на a, либо на b. Это
количество можно вычислить по формуле:
n / a + n / b – n
/ НОК(a,
b)
Пусть x – искомое n-ое число,
которое делится или на a, или на b. Тогда x –наименьшее натуральное число, для которого выполняется условие f(x) = n. Его будем искать с помощью
бинарного поиска на отрезке [left; right] = [1; 109]. На каждом
шаге вычисляем mid = (left + right) / 2. Если f(mid) ≥
n, продолжаем поиск в левом
подотрезке [left; mid], иначе – в правом подотрезке [mid + 1; right].
Пример
Рассмотрим первый пример, в
котором a = 2, b = 5. Необходимо найти наименьшее значение x, для которого выполняется условие f(x) = 10. Вычислим
значения функции f(x) для некоторых x:
·
f(15)
= 15 / 2 + 15 / 5 – 15 / 10 = 7 + 3 – 1 = 9;
·
f(16)
= 16 / 2 + 16 / 5 – 16 / 10 = 8 + 3 – 1 = 10;
·
f(17)
= 17 / 2 + 17 / 5 – 17 / 10 = 8 + 3 – 1 = 10;
·
f(18)
= 18 / 2 + 18 / 5 – 18 / 10 = 9 + 3 – 1 = 11;
Наименьшим решением уравнения f(x)
= 10 будет x = 16.
Реализация алгоритма
Функции gcd и lcm вычисляют соответственно НОД и НОК.
long long gcd(long long a, long long b)
{
return (b == 0) ? a : gcd(b, a % b);
}
long long lcm(long long a, long long b)
{
return a /
gcd(a, b) * b;
}
Функция f(n) возвращает количество натуральных чисел, не превышающих n и делящихся либо на a, либо на b.
long long f(long long n)
{
return n / a
+ n / b - n / lcm(a, b);
}
Читаем входные данные.
scanf("%lld %lld %lld",
&a, &b, &n);
Запускаем бинарный поиск на отрезке [left; right] = [1; 109]. Ищем наименьшее значение left, при котором
выполняется условие f(left)
= n.
left = 1; right = 1e9;
while (left < right)
{
middle
= (left + right) / 2;
if
(f(middle) >= n)
right
= middle;
else
left
= middle + 1;
}
Выводим ответ.
printf("%lld\n",
left);
Java реализация
import java.util.*;
import java.io.*;
public class Main
{
static long gcd(long a, long b)
{
return (b ==
0) ? a : gcd(b, a % b);
}
static long lcm(long a, long b)
{
return a / gcd(a, b) * b;
}
static long f(long n, long a, long b)
{
return n / a + n / b - n / lcm(a, b);
}
public static void
main(String[] args)
{
FastScanner con = new
FastScanner(new InputStreamReader(System.in));
long a = con.nextInt();
long b = con.nextInt();
long n = con.nextInt();
long left = 1,
right = 1000000000;
while (left <
right)
{
long middle = (left + right) /
2;
if (f(middle, a, b)
>= n)
right = middle;
else
left = middle + 1;
}
System.out.println(left);
}
}
class FastScanner
{
private BufferedReader br;
private StringTokenizer st;
public
FastScanner(InputStreamReader reader)
{
br = new BufferedReader(reader);
}
public
String next()
{
while (st == null || !st.hasMoreTokens())
{
try
{
st = new StringTokenizer(br.readLine());
} catch
(Exception e)
{
e.printStackTrace();
}
}
return st.nextToken();
}
public int nextInt()
{
return Integer.parseInt(next());
}
public void
close() throws Exception
{
br.close();
}
}